
\section{A protocol for validator selection in NPoS}\label{s:objectives}

In this section we provide high-level details of a proposal for a validator selection protocol in an NPoS-based blockchain network. This proposal will be the basis for an implementation in the Polkadot network.

A committee of $k$ validators is selected once per era, where an era is multiple hours or days long. 
In each era, a group of off-chain workers each privately runs the election algorithm for the next era, and submits its solution on-chain. 
We propose that each validator act as an off-chain worker and run such computation, but this need not be the case. 
More in detail, towards the end of each era there is an \emph{election window} where the following events occur:
\begin{enumerate}
\item The chain fixes the (otherwise ever-evolving) set of validator candidates and nominators' preferences and stake to be considered for the election, ignoring any further changes in the remainder of the era. 
\item All current validators trigger an off-chain execution of the $\balanced$ election rule, separate from block production and other duties.
\item Once the solutions are computed (after a few seconds of the start of the election window), validators submit them on-chain as a special type of transaction. 
\item On the on-chain side, we only keep track of one solution at any given time, which is the current tentative winner. Specifically, if $(A_t,w_t)$ is the tentative winner recorded on-chain, a block producer can include a new solution $(A,w)$ to its block only if a) it is feasible, b) $supp_w(A)>supp_{w_t}(A_t)$, and c) it passes the test described in Theorem~\ref{thm:315guarantee}. If this is the case, $(A,w)$ replaces $(A_t, w_t)$ as the current tentative winner. 
\item At the end of the election window, the current tentative winner is declared the official winner. 
\end{enumerate}

We make a few remarks about this protocol. 
\begin{itemize}
\item By Theorem \ref{thm:315guarantee}, the protocol will elect a solution that simultaneously satisfies the PJR property and a 3.15-factor approximation for the maximin support problem. These constitute strong and formal guarantees on security and proportionality. 
\item On top of the guarantees above, we are bound to elect the best solution found by anyone. In particular, validators may find diverse solutions due to different tie-breaking rules, or more explicit deviations from the suggested algorithm. However, as long as we rank solutions objectively and pick the best one, any diversity in solutions can only improve the quality of the winning committee, and thus benefits the community.
\item The fact that the guarantees on security and proportionality are verifiable protect the network against a \emph{long range attack}, i.e. a scenario where an adversary creates a branch of the blockchain which is grown in secret, with the intention to eventually make it public and have it overtake the main chain. In particular, if the protocol limited itself to select the best solution submitted by validators without a verification of guarantees, an adversary could use a long range attack to create a branch in which, during an election window, it censors all solutions coming from honest validators and thus makes the protocol elect a committee where the adversary is heavily overrepresented.
\item On the on-chain side, the election protocol runs in linear time $O(|E|)$ per block, by Theorem \ref{thm:315guarantee} and the fact that at most one solution is verified per block.  
\end{itemize}

Next, we suggest additional variations and optimizations:
\begin{itemize}
\item We suggest that instead of gossiping a solution over the network as a transaction, each validator waits for its turn to be a block producer to submit its own solution. Doing so saves communication overhead, as election solutions make for rather heavy transactions. In this case, it is important that the election window is long enough so that with high probability each validator gets to produce a block, and thus is not censored. 
The system can still receive solutions as transactions from arbitrary users, but in this case the transaction fee must be high to protect against spamming attacks. 
\item For any weight vector $w\in \R^E$, let $E_w$ denote its edge support, i.e. $E_w:=\{e\in E: \ w_e>0\}$, and notice that the size of a solution $(A,w)$ is dominated by the size of its edge support $|E_w|$. 
However, by removing circulations, from any feasible vector $w$ one can compute another feasible vector $w'\in\R^E$ such that a) all supports are preserved, i.e. $supp_w(c)=supp_{w'}(c)$ for each $c\in C$, and b) $E_{w'}$ is a forest, and hence $|E_{w'}|< |N|+k=O(|N|)$, where we assume that $|N|\geq k$. Therefore, validators can run this post-computation off-chain to reduce the size of any solution to $O(|N|)$, thus saving space on the block.

\item Recall that on the on-chain side, for a new solution $(A,w)$ we check a) feasibility, b) its objective value (and whether it beats the current tentative winner), and c) the test in Theorem~\ref{thm:315guarantee}. Notice that the third check runs in time $O(|E|)$ and thus is considerably slower than the first two checks, which run in time $O(|E_w|)$, with $O(|E_w|)=O(|N|)$ if the previous suggestion is implemented. 
A possible optimization is as follows: the chain requires the first submitted solution $(A_0, w_0)$ to pass all three checks, and then skips the third check on all subsequent solutions, so that their processing time drops to $O(|N|)$. At the end of the election window, we check whether the current tentative winner $(A_t, w_t)$ satisfies PJR with the condition on Lemma~\ref{lem:locality}. 
We can expect that this check is always passed. In the unlikely case that $(A_t, w_t)$ fails this condition, the election window is extended for a few more minutes and validators are asked to run the post-computation $\local$ over it off-chain. 
The window ends as soon as some block producer submits a feasible solution $(A_T, w_T)$ such that $supp_{w_T}(A_T)\geq supp_{w_t}(A_t)$ and which satisfies PJR as attested by the condition on Lemma~\ref{lem:locality}. 
With this optimization, the runtime drops to $O(|N|)$ per block, except for two or possibly three blocks with a runtime of $O(|E|)$, and we keep all guarantees, namely that the winning committee a) is at least as good as all submitted solutions, b) satisfies PJR, and c) is a 3.15-factor approximation for maximin support (as its objective value is at least as good as that of the first solution $(A_0, w_0)$, which passed the test in Theorem~\ref{thm:315guarantee}). 

\item In terms of incentives, the system can provide an economic reward to the submitter of each tentative winning solution, with larger rewards for the first and the last one to encourage early submissions and good submissions respectively. If the previous suggestion is implemented and a solution $(A_t, w_t)$ fails the test on Lemma~\ref{lem:locality}, a heavy fine should be charged to the submitter. 
\end{itemize}